#include "htree.h"
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <stdio.h>
#include <fcntl.h>
#include <sys/stat.h>
#include <unistd.h>
int xhash(const void *cstr,size_t key_len){
  char *pstr=(char *)cstr;
  int h = 5381;
  if(key_len == 0){
    return (h << 5);
  }

  int off = 0;
  int i=0;
  for (; i < key_len; i++) {
    h = (h << 5) + h + pstr[off++];
  }

  return h;
}

static char prim[]={
		2,   3,   5,   7,   11,  13,  17,  19,  23,
		29,  31,  37,  41,  43,  47,  53,  59,  61,
		67,  71,  73,  79,  83,  89,  97,  101, 103,
		107, 109, 113, 127, 131, 137, 139, 149, 151,
		157, 163, 167, 173, 179, 181, 191, 193, 197,
		199, 211, 223, 227, 229, 233, 239, 241, 251};
static const int LVL_MAX=54;
		
struct h_node* new_hnode(){
	static size_t size=sizeof(struct h_node); 
	struct h_node *node=(struct h_node*)malloc(size);
	if(node){
		node->used=0;
		memset(node->key,0,128);
		node->value=0;
		node->subnodes=NULL;
		node->num=0;
		node->brother=NULL;
		node->hash=0;
	}
	return node;
}

static int write_data(struct h_tree *tree,struct buffer *buff){
	int fd=tree->wr_fd;
	unsigned long off_wr=tree->wr_index;
	
	ready_to_write(buff);
	char *data_ref=buff->data;
	int wr_len= buff->limit - buff->index;
	while(wr_len){
		int ret=write(fd,data_ref + buff->index,wr_len);
		if(ret == -1){
			if(errno==EAGAIN){continue;}
			if(errno==EINTR){continue;}
			tree->wr_index=off_wr;
			close(fd);
			return -1;
		}
		if(ret == 0){
			continue ;
		}
		tree->wr_index = tree->wr_index + ret;	
		if(ret == wr_len){
			return 0;
		}
		wr_len = wr_len - ret;
		buff->index =  buff->index + ret;
	}
	return 0;
}
static void save_idx(int fd,struct h_node *node){
	write(fd,&(node->used),1);
	write(fd,node->key,128);
	int is_big = is_big_cpu();
	char val[16];
	
	if(is_big){		
		//val[0]=(char)((node->value)>>56);
		//val[1]=(char)((node->value)>>48);
		//val[2]=(char)((node->value)>>40);
		//val[3]=(char)((node->value)>>32);
		val[4]=(char)((node->value)>>24);
		val[5]=(char)((node->value)>>16);
		val[6]=(char)((node->value)>>8);
		val[7]=(char)(node->value);

		//val[8]=(char)((node->dat_len)>>56);
    		//val[9]=(char)((node->dat_len)>>48);
    		//val[10]=(char)((node->dat_len)>>40);
    		//val[11]=(char)((node->dat_len)>>32);
		val[12]=(char)((node->dat_len)>>24);
		val[13]=(char)((node->dat_len)>>16);
		val[14]=(char)((node->dat_len)>>8);
		val[15]=(char)(node->dat_len);

  	}else{
    		val[0]=(char)(node->value);
    		val[1]=(char)((node->value)>>8);
    		val[2]=(char)((node->value)>>16);
    		val[3]=(char)((node->value)>>24);
		//val[4]=(char)((node->value)>>32);
    		//val[5]=(char)((node->value)>>40);
    		//val[6]=(char)((node->value)>>48);
    		//val[7]=(char)((node->value)>>56);

		val[8]=(char)(node->dat_len);
    		val[9]=(char)((node->dat_len)>>8);
    		val[10]=(char)((node->dat_len)>>16);
    		val[11]=(char)((node->dat_len)>>24);
		//val[12]=(char)((node->dat_len)>>16);
		//val[13]=(char)((node->dat_len)>>40);
		//val[14]=(char)((node->dat_len)>>48);
		//val[15]=(char)((node->dat_len)>>56);
  	}
	write(fd,val,16);
}
//TODO read more data to a linked table struct buffer from disk
static int read_data(struct h_tree *tree,struct buffer *buff){
	int fd = tree->rd_fd;
	unsigned long off_rd=tree->rd_index;
	int rd_len= buff->limit;
	char *data_ref=buff->data;

	while(rd_len){
		int ret=read(fd,data_ref + buff->index,rd_len);
		if(ret == -1){
			if(errno==EAGAIN){continue;}
			if(errno==EINTR){continue;}
			tree->rd_index=off_rd;
			close(fd);
			return -1;
		}
		if(ret == 0){
			tree->rd_index=off_rd;
			return 1;
		}
		rd_len = rd_len - ret;
		buff->index =  buff->index + ret;
	}
	return 0;
}

int save_node(struct h_tree *tree,struct h_node *node,const char *key, struct buffer *val,int hash ){
	node->used=1;
	strcpy(node->key,key);
	node->hash = hash;
	node->value = tree->wr_index;
	
	while(val){
		node->dat_len += val->index;
		write_data(tree,val);
		val = val->next;
	}

	printf("off %ld len %ld\n",node->value,node->dat_len);
	return 0;
}

struct h_node* locate_4_write(struct h_node *node,int *lvl,const char *key,int key_hash){
	if(!(node->used)){// 没有占用
		return node;
	}
	
	if(key_hash == node->hash){// hash值虽然相同，key也有可能不同
		int res=strcmp(node->key,key);
		if(res==0){
			return node;
		}
	}
	(*lvl)++;
	if((*lvl)>=LVL_MAX){//到达层数上限
		return NULL;
	}
	//key不同相同，在他的子节点找
	unsigned char sub_count=prim[*lvl];
	int num = key_hash % sub_count;
	if(!(node->subnodes)){//没有子节点创造一个子节点
		struct h_node *_node = new_hnode();
		_node->num=num;
		node->subnodes=_node;
		return node->subnodes;
	}

	struct h_node *temp=node->subnodes;
	while(temp){
		if(num!=temp->num){// 不是选中的号码，查看下一个兄弟节点
			temp=temp->brother;
			continue;
		}
		return locate_4_write(temp,lvl,key,key_hash);
	}
	struct h_node *_node=new_hnode();
	_node->num=num;
	temp=node->subnodes;
	node->subnodes=_node;
	_node->brother=temp;
	return _node;
}
struct h_node* locate_4_read(struct h_node *node,int *lvl,const char *key,int key_hash){
	if(node->used){//占用
		if(key_hash == node->hash){
			int res=strcmp(node->key,key);
			if(res==0){// hash值相同，key也同
				return node;
			}
		}
	}
	
	(*lvl)++;
	if((*lvl)>=LVL_MAX){//到达层数上限
		return NULL;
	}
	//key不同相同，在他的子节点找
	unsigned char sub_count=prim[*lvl];
	int num = key_hash % sub_count;
	if(!(node->subnodes)){//没有子节点
		return NULL;
	}

	struct h_node *temp=node->subnodes;
	while(temp){
		if(num!=temp->num){// 不是选中的号码，查看下一个兄弟节点
			temp=temp->brother;
			continue;
		}
		return locate_4_read(temp,lvl,key,key_hash);
	}
	return NULL;
}


struct h_tree* new_htree(){
	size_t size=sizeof(struct h_tree);
	struct h_tree *tree=(struct h_tree*)malloc(size);
	
	struct h_node *root= new_hnode();
	tree->root=root;
	tree->idx_fd=open("kv.idx",O_RDWR|O_CREAT,S_IRUSR|S_IWUSR);
	return tree;
}

int save(struct h_tree *tree,const void *key,size_t key_len, struct buffer *val){
	int lvl=0;
	int hash=xhash(key,key_len);
	struct h_node *node=locate_4_write(tree->root,&lvl,key,hash);
	save_node(tree,node,key, val,hash );
	save_idx(tree->idx_fd,node);
	return 0;
}

int find(struct h_tree *tree,const void *key,size_t key_len, struct buffer *val){
	int lvl=0;
	int hash=xhash(key,key_len);
	struct h_node *node=locate_4_read(tree->root,&lvl,key,hash);
	if(!node){
		return 1;
	}
	ready_to_read(val);
	val->limit = node->dat_len;
	lseek(tree->wr_fd,node->value,SEEK_SET);
	read_data(tree,val);
	return 0;
}

int take(struct h_tree *tree,const void *key,size_t key_len){
	int lvl=0;
	int hash=xhash(key,key_len);
	struct h_node *node=locate_4_write(tree->root,&lvl,key,hash);
	if(!node){
		return 1;
	}
	printf("take___lvl %d:key %s :value s \n",lvl,node->key);
	node->used=0;
	return 0;
}



